Crate num_prime

This crate provides utilities for prime related functionalities and some basic number theoretic functions:

• Primality testing
  • Primality check
  • Deterministic primality check of u64 integers (using a very fast hashing algorithm)
  • Fermat probable prime test
  • Miller-rabin probable prime test
  • (strong/extra strong) Lucas probable prime test
  • Baillie-PSW test
  • Sophie Germain safe prime test
• Primes generation and indexing
  • A naive implementation of the sieve of Eratosthenes
  • Unified API to support other prime generation backends
  • Generate random (safe) primes
  • Find previous prime / next prime
• Integer factorization
  • Trial division
  • Pollard’s rho algorithm
  • Shanks’s square forms factorization (SQUFOF)
  • Hart’s one line algorithm
  • Fast factorization of u64 integers
• Number theoretic functions
  • Prime Pi function, its estimation, and its bounds
  • Nth Prime, its estimation, and its bounds
  • Moebius function

Usage

Most number theoretic functions can be found in nt_funcs module, while some of them are implemented as member function of num_modular::ModularOps or PrimalityUtils.

Example code for primality testing and integer factorization:

use num_prime::{PrimalityTestConfig, FactorizationConfig};
use num_prime::nt_funcs::{is_prime, factorize, factors};

let p = 2u128.pow(89) - 1; // a prime number
assert!(is_prime(&p, None).probably()); // use default primality check config
assert!(is_prime(&p, Some(PrimalityTestConfig::bpsw())).probably()); // BPSW test

let c = 2u128.pow(83) - 1; // a composite number
assert!(!is_prime(&c, None).probably());
let fac = factorize(c); // infallible factorization with default configuration
assert_eq!(fac.len(), 2); // 2^83-1 = 167 * 57912614113275649087721

let config = FactorizationConfig::strict();
let (fac, rem) = factors(c, Some(config)); // fallible factorization with customized configuration
assert!(fac.len() == 2 && rem.is_none());

Backends

This crate is built with modular integer type and prime generation backends. Most functions support generic input types, and support for num-bigint is also available (it’s an optional feature). To make a new integer type supported by this crate, the type has to implement detail::PrimalityBase and detail::PrimalityRefBase. For prime generation, there’s a builtin implementation (see buffer module), but you can also use other backends (such as primal) as long as it implements PrimeBuffer.

Optional Features

• big-int (default): Enable this feature to support num-bigint::BigUint as integer inputs.
• big-table (default): Enable this feature to allow compiling large precomputed tables which could improve the speed of various functions with the cost of larger memory footprint.

Modules

• buffer
  Implementations and extensions for PrimeBuffer, which represents a container of primes
• detail
  Implementation details for this crate.
• factor
  Implementations for various factorization algorithms.
• nt_funcs
  Standalone number theoretic functions

Structs

• FactorizationConfig
  Represents a configuration for integer factorization
• PrimalityTestConfig
  Represents a configuration for a primality test

Enums

• Primality
  This enum describes the result of primality checks

Traits

• BitTest
  This trait support unified bit testing for (unsigned) integers
• ExactRoots
  Extension on num_integer::Roots to support perfect power check on integers
• PrimalityUtils
  This trait implements various primality testing algorithms
• PrimeBuffer
  This trait represents a general data structure that stores primes.
• RandPrime
  Supports random generation of primes